//
// Created by zhulingfeng on 2020/2/26.
//

#include "insertion_sort.hpp"
void Merge(std::vector<int> &vector, std::vector<int> &aux, int lo, int mid,
           int hi) {
  // If subarray is already sorted, return;
  if (vector[mid] <= vector[mid + 1]) return;
  int i = lo;
  int j = mid + 1;
  for (int k = lo; k <= hi; k++) {
    aux[k] = vector[k];
  }
  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      vector[k] = aux[j++];
    else if (j > hi)
      vector[k] = aux[i++];
    else if (aux[i] <= aux[j])
      vector[k] = aux[i++];
    else
      vector[k] = aux[j++];
  }
}

void MergeSort(std::vector<int> &vector, std::vector<int> &aux, int lo,
               int hi) {
  if (lo >= hi) return;
  const int kSizeThreshold = 20;
  // Use insertion sort when subarray is small.
  if (hi - lo < kSizeThreshold) {
    InsertionSort(vector, lo, hi);
    return;
  }
  int mid = (lo + hi) / 2;
  MergeSort(vector, aux, lo, mid);
  MergeSort(vector, aux, mid + 1, hi);
  Merge(vector, aux, lo, mid, hi);
}

void MergeSortRecursively(std::vector<int> &vector) {
  std::vector<int> aux(vector.size());
  MergeSort(vector, aux, 0, vector.size() - 1);
}

void MergeSortIteratively(std::vector<int> &vector) {
  int n = vector.size();
  std::vector<int> aux(n);
  for (int sz = 1; sz < n; sz *= 2) {
    for (int lo = 0; lo < n - sz; lo += (2 * sz)) {
      const int kSizeThreshold = 15;
      int hi = std::min(lo + sz + sz - 1, n - 1);
      // Use insertion sort when subarray is small.
      if (hi - lo < kSizeThreshold) {
        InsertionSort(vector, lo, hi);
        continue;
      }
      Merge(vector, aux, lo, lo + sz - 1, std::min(lo + sz + sz - 1, n - 1));
    }
  }
}

void MergeWithoutCopy(std::vector<int> &to, std::vector<int> &from, int lo,
                      int mid, int hi) {
  // If subarray is already sorted, copy.
  if (from[mid] <= from[mid + 1]) {
    for (int i = lo; i <= hi; i++) {
      to[i] = from[i];
    }
    return;
  }
  int i = lo;
  int j = mid + 1;
  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      to[k] = from[j++];
    else if (j > hi)
      to[k] = from[i++];
    else if (from[i] <= from[j])
      to[k] = from[i++];
    else
      to[k] = from[j++];
  }
}

void MergeSortIterativelyWithoutCopy(std::vector<int> &vector) {
  int n = vector.size();
  if (n <= 1) return;
  std::vector<int> aux(n);
  auto from = &vector;
  auto to = &aux;
  auto last_to = to;
  for (int sz = 1; sz < n; sz *= 2) {
    int lo = 0;
    for (; lo < n - sz; lo += (2 * sz)) {
      MergeWithoutCopy(*to, *from, lo, lo + sz - 1,
                       std::min(lo + sz + sz - 1, n - 1));
    }
    if (lo < n) {
      // Copy the last part that no need to merge.
      for (int i = lo; i < n; i++) (*to)[i] = (*from)[i];
    }
    last_to = to;
    to = from;
    from = last_to;
  }
  if (last_to == &aux) vector = aux;
}

ListNode *FindMiddle(ListNode *head, int &size) {
  size = 0;
  if (!head) return nullptr;
  auto fast = head->next;
  while (fast && fast->next) {
    size += 2;
    head = head->next;
    fast = fast->next->next;
  }
  return head;
}

ListNode *Merge(ListNode *lh, ListNode *rh) {
  ListNode dummy;
  auto tail = &dummy;
  while (lh && rh) {
    if (lh->val <= rh->val) {
      tail->next = lh;
      lh = lh->next;
    } else {
      tail->next = rh;
      rh = rh->next;
    }
    tail = tail->next;
  }
  tail->next = lh ? lh : rh;
  return dummy.next;
}

ListNode *MergeSortRecursively(ListNode *head) {
  if (!head || !head->next) return head;
  int size = -1;
  auto mid = FindMiddle(head, size);
  const int kSizeThreshold = 15;
  // Use insertion sort when subarray is small.
  if (size < kSizeThreshold) {
    return InsertionStableSort(head);
  }
  auto rh = mid->next;
  // Split list to two sub-lists, with nullptr in list end, enabling Merge()
  // to judge the end of sub-list.
  mid->next = nullptr;
  head = MergeSortRecursively(head);
  rh = MergeSortRecursively(rh);
  return Merge(head, rh);
}
